<?php
/**
 * @title 56. 合并区间 - 遍历
 * @author start2004
 */

class Solution {

    /**
     * @param Integer[][] $intervals
     * @return Integer[][]
     */
    function merge($intervals) {
        /**
         * @since 2020-09-16 长度
         */
        $len = count($intervals);
        if($len == 0){
            return [];
        } else {}

        /**
         * @since 2020-09-16 按起点排序
         */
        $lefts = array_column($intervals, 0);
        array_multisort($intervals, SORT_ASC, SORT_NUMERIC, $lefts);

        /**
         * @since 2020-09-16 结果集
         */
        $result = [];

        /**
         * @since 2020-09-16 合并区间
         */
        list($left1, $right1) = $intervals[0];
        for ($i=1; $i<$len; $i++){
            list($left2, $right2) = $intervals[$i];

            /**
             * @since 2020-09-16 能否合并
             */
            if($right1>=$left2){
                $right1 = max($right1, $right2);
            } else {
                /**
                 * @since 2020-09-16 无法合并
                 */
                $result[] = [$left1, $right1];

                /**
                 * @since 2020-09-16 新的起点区间
                 */
                $left1 = $left2;
                $right1 = $right2;
            }
        }

        /**
         * @since 2020-09-16 收官
         */
        $result[] = [$left1, $right1];

        /**
         * @return
         */
        return $result;
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.23_9.php
 */
$datas = [
    [[1,3],[2,6],[8,10],[15,18]],
    [[1,4],[4,5]],
    [[5,6],[2,3],[4,6],[3,5],[1,3]],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->merge($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
